1977C - Nikita and LCM - CodeForces Solution

from math import gcd
from collections import defaultdict

def lcm(x, y):
    return x*y//gcd(x, y)

def solution():
    n = int(input())
    a = list(map(int, input().split()))
    mx = max(a)
    dp = defaultdict(int)
    for x in a:
        new_dp = dp.copy()
        new_dp[x] = max(new_dp[x], 1)
        for y, cnt in dp.items():
            l = lcm(x, y)
            if l > mx:
                return n
            new_dp[l] = max(new_dp[l], cnt+1)
        dp = new_dp
    lookup = set(a)
    return max((cnt for x, cnt in dp.items() if x not in lookup), default=0)

for _ in range(int(input())):
    print(solution())